class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        // 首先从右往左寻找第一个满足 nums[i+1] > nums[i] 的元素
        int k = nums.size() - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--;
        }
        
        // 如果 k < 0，说明整个数组都是降序排列，翻转整个数组
        if (k < 0) {
            reverse(nums.begin(), nums.end());
        } else {
            // 找到了这样的元素
            // 从右往左寻找比 nums[k] 大的元素
            int j = nums.size() - 1;
            while (j >= 0 && nums[j] <= nums[k]) {
                j--;
            }
            // 交换两个元素
            swap(nums[j], nums[k]);
            // 对 k 后面的元素进行反转
            reverse(nums.begin() + k + 1, nums.end());
        }
    }
};
